|
B+木（）は、キーを指定することで挿入・検索・削除が効率的に行える木構造の一種である。動的な階層型インデックスであり、各インデックスセグメント（「ブロック」などと呼ばれる。木構造におけるノードに相当）にはキー数の上限と下限がある。B+木はB木とは異なり、全てのレコードは木の最下層（葉ノード）に格納され、内部ノードにはキーのみが格納される。 B+木は、特にブロック型記憶装置での効率的データ検索に効果を発揮する。ブロックサイズ の記憶装置があるとき、 の倍数個のキーを格納するB+木は2分探索木に比較して非常に効率が良い（2分探索木はブロック型でない記憶装置に適している）。 ReiserFS（UNIX、Linux）、XFS（IRIX、Linux）、JFS2（AIX、OS/2、Linux）、HammerFS（DragonFly BSD）、NTFSといったファイルシステムはいずれもB+木に類する構造をブロックのインデックス付けに使っている。関係データベースでも表のインデックスにこの種の木構造を使っていることが多い。 == 詳細 == B+木の次数は木構造内のノードの容量の尺度である。次数を ''d'' としたとき、''d'' <= ''m'' <= 2 ''d'' となるような ''m'' が各ノードのエントリ数となる。例えば、次数7のB+木があるとき、根ノード以外の内部ノードは7個から14個のキーを格納する。根ノードは1個から14個のキーを格納する。 さらに各内部ノードは、最低でも ''d''+1 個、最高でも 2''d''+1 個の子ノードを持つ。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「B+木」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 B+ tree 」があります。 スポンサード リンク
|